#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "hash_table.h"

unsigned int hash(char *str)
{
	register unsigned int h;
	register unsigned char *p; 

	for(h=0, p = (unsigned char *)str; *p ; p++)
		h = 31 * h + *p; 

	return h;
}

hashtable* ht_create(int size)
{
	int			i;
	hashtable 	*table;

	table = (hashtable *)malloc(sizeof(hashtable));
	if (table == NULL) return NULL;
	table->buckets = (ht_bucket **)malloc(sizeof(ht_bucket* )*size);
	if (table->buckets == NULL) {
		free(table);
		return NULL;
	}

	for (i = 0; i < size; i++) {
		table->buckets[i] = NULL;
	}
	table->n = 0;
	table->nhash = 0;
	table->size = size;

	return table;
}

int ht_insert(hashtable *table, char *key, char *data)
{
	int 		i;
	ht_bucket	*bucket;
	
	i = hash(key) % table->size;
	//printf("%s插入%d...\n", key, i);
	if (table->buckets[i] == NULL) {
		table->nhash++;
		//printf("位置%d未使用\n", i);
	}
	else {
		//printf("位置%d有冲突\n", i);
	}
	for (bucket = table->buckets[i]; bucket != NULL && 
			strcmp(bucket->key, key) != 0; bucket = bucket->next);
	if (bucket == NULL) {
		//printf("没有相同的key\n");
		bucket = (ht_bucket *)malloc(sizeof(ht_bucket));
		strcpy(bucket->key, key);
		if (data) strcpy(bucket->data, data);
		bucket->next = table->buckets[i];
		table->buckets[i] = bucket;;
		table->n++;
		return 1;
	}
	//printf("存在相同的key\n");
	return 0;
}

char *ht_find(hashtable *table, char *key)
{
	int			i;
	ht_bucket	*bucket;

	i = hash(key) % table->size;
	if (table->buckets[i] == NULL) {
		return NULL;
	}
	for (bucket = table->buckets[i]; bucket != NULL && 
			strcmp(bucket->key, key) != 0; bucket = bucket->next);
	if (bucket == NULL) {
		return NULL;
	}
	return bucket->data;
}

void ht_destroy(hashtable *table)
{
	int		i, n;
	ht_bucket	*p, *q;

	for (i = 0; i < table->size; i++) {
		if (table->buckets[i]) {
			//printf("位置%d有数据\n", i);
		}
	}
	for (i = 0; i < table->size; i++) {
		n = 1;
		for (p = table->buckets[i]; p;) {
			q = p;
			p = p->next;
			//printf("销毁位置%d的第%d个bucket\n", i, n++);
			free(q);
		}
	}
	free(table->buckets);
	free(table);
}
